#!/usr/bin/env python3

"""
A robot is located at the top-left
"""

class Solution:
    def uniquePaths(self, m, n):
        cache = {}
        return self.num_of_paths(m - 1, n - 1, cache)

    def num_of_paths(self, left_num, down_num, cache):
        if left_num == 0 or down_num == 0:
            return 1
        if (left_num, down_num) in cache:
            return cache[(left_num, down_num)]
        result =  self.num_of_paths(left_num - 1, down_num, cache) \
            + self.num_of_paths(left_num, down_num - 1, cache)
        cache[(left_num, down_num)] = result
        return result
        


if __name__ == '__main__':
    s = Solution()
    print(str(s.uniquePaths(23, 12)))
    assert 3 == s.uniquePaths(3, 2)
